#include<bits/stdc++.h>
using namespace std;

struct node {
	int data;
	int next, pre;
} a[1000005];

signed main() {
	int n, m;
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) {
		a[i] = {i, i + 1, i - 1};
	}

	int k;
	while (m--) {
		scanf("%d", &k);
		int t1 = a[k].pre;
		int t2 = a[k].next;
		if (t1 >= 1)
			printf("%d ", a[t1].data);
		else
			printf("* ");
		if (t2 <= n)
			printf("%d\n", a[t2].data);
		else
			printf("*\n");

		a[t1].next = a[k].next;
		a[t2].pre = a[k].pre;
	}
	return 0;
}
